package com.lc.lc22;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		List<String> list = new Solution().generateParenthesis(1);
		System.out.println(list);
	}

}


class Solution {
	List<String> resList;
	int n;
	
	boolean check(String s) {
		int cnt = 0;
		for (int i = 0; i < n; i ++) {
			if (s.charAt(i) == '(') {
				cnt ++;
			} else {
				if (cnt == 0) {
					return false;
				} else {
					cnt --;
				}
			}
		}
		return cnt == 0;
	}
	
	void dfs(String path) {
		if (path.length() == n) {
			if (check(path)) {
				resList.add(path);
			}
			return;
		}
		dfs(path + '(');
		dfs(path + ')');
	}
	
    public List<String> generateParenthesis(int n) {
    	this.n = 2 * n;
    	this.resList = new ArrayList<>();
    	dfs("");
    	return resList;
  
    }
}
